A local area network (LAN) is a data-communications network which is generally thought of as being limited to a relatively small geographical area. Because of this geographic concentration, LANs differ from long-distance networks in a number of respects. For example, there exists more freedom in determining the topology of a LAN because nodes do not necessarily have to be connected to their closest neighbors if doing so makes routing more complicated. Error rates tend to be lower in LANs than in long-distance networks. Consequently, error checking can be done on an end to end, rather than a link by link, basis. Also a LAN can utilize less expensive communications lines.
The evolution of personal computers and the more widespread use of computers in general have given rise to a need for LANs with higher throughput and reliability than those developed a decade or more ago. The complexity of the devices being connected to networks and advances in VLSI make more complex network interfaces feasible, thus increasing the number of network structures and access strategies that can be considered.
The star, ring, bus, and tree topologies are four standard LAN structures currently being used. The star topology consists of a central switch, or hub, with links connecting the hub to each of the devices. A packet transmitted from any device must pass through the hub to its destination. The hub, therefore, is the central controller of the system. A ring, or loop, topology comprises a series of unidirectional links connecting Ring Interface Units which are in turn connected to devices. A bus topology is a long transmission channel to which all of the devices are attached through Bus Interface Units. The devices contend for access to the bus and the choice of a winner must be based on a priorily specified rules. Lastly, a tree structure comprises links interconnected like branches on a tree. In this structure, a packet travels from its originating node to the root, or head end, of the tree and is then retransmitted down the tree to its destination.
These topologies have several disadvantages. With buses and rings, the fraction of the network used to transmit each packet is very high. Consequently, very few messages, or in some cases just one, can be transmitted at a time. The star topology provides an improvement in this respect. A smaller fraction of the network is used for each transmission, but all transmitted packets must pass through the central hub. The central controller, hence, is the bottleneck which limits the number of packets that can be transmitted simultaneously. A similar situation exists with the tree topology.
Another alternative is a new tree topology being investigated by Yemini in "Tinkernet: Or Is There Life Between LANs and PBXs," Proc. ICC 1983, Vol. 3, (Boston, June, 1984), pp. 1501-5, and a variation thereof by Saadawi and Schwartz in "Distributed Switching for Data Transmission Over Two-Way CATV," Proc. ICC 1984, (Amsterdam, May, 1984), pp. 1409-13. In these networks, the nodes are switching points, eliminating the need for every packet to pass through the head end. Although this approach utilizes a smaller fraction of the network for each message and requires only one type of element, it must either store and forward packets (Saadawi) or retain the distance constraints of broadcast networks (Yemini).
To a certain extent these alternatives remove the throughput constraints of ring and bus systems. However, they still have single points of failure. To increase the network's reliability, or the number of links or nodes that can fail without a substantial loss in efficiency, there must be multiple paths between each source and destination. By increasing the number of paths properly, the average and maximum distances between nodes decrease, messages use of smaller fraction of the network, and the throughput increases. Multiple paths also make it possible to avoid heavily used segments of the network to equalize the load.
Another attempt at a solution is the bidirectional loop. It consists of a plurality of nodes connected in a circle by bidirectional paths. This network is defined for any number of nodes and makes geographical sense. It also has simple expanding and routing rules although these two functions complicate each other. The routing rule depends on the sequential addressing of the nodes, but these addresses change when the network is expanded. Consequently, either a routing rule which does not depend on the node addresses must be adopted or a new set of addresses must be distributed each time the network is changed. Moreover, there exist only two different paths between any two nodes.
Another, more effctive, attempt at a solution is set forth by Pierce in "How Far Can Loops Go," IEEE Trans. on Comm., Vol. M-20, No. 3, June, 1972, pp. 527-530. His topology consists of a plurality of loops interconnected by switching elements. Messages use a smaller fraction of the total network than they would if the system were a single loop, thereby increasing the maximum throughput. Interference between subgroups of users is minimized by placing user who communicate primarily with each other on the same loop. The main disadvantage with this approach is that it requires two different types of elements--those for switching and those for access to devices. Also, the swtiching elements must have complex store and forward capabilities.
A general class of LAN topologies which provide for multiple paths between nodes and overcome many of the disadvantages of the multiple loop and tree systems described above are mesh LANs. Mesh LANs have no central node and consist of point to point communication channels between nodes, thus requiring less expensive line drivers and receivers. In addition, their structure makes numerous long connections unnecessary and can take advantage of the natural formation of communities of interest, or groups of nodes who communicate primarily with each other. It is comparatively easy to add nodes to a mesh LAN and these networks are very adaptable to new fiber optics technology.
One implementation of a mesh LAN, called FLOODNET, is described by Petitpierre in "Meshed Local Computer Networks, IEEE Comm. Mag., Vol. 22, No. 8, (August, 1984), pp. 36-40. In FLOODNET, when a packet comes into a node, it is retransmitted on all lines emanating from the node except the one on which the packet arrived. A routine for eliminating extraneous packets must be implemented. Each packet then "floods" the entire network.
The modified shuffle exchange network is another network characterized by a mesh topology. It is defined for N nodes where N is strictly a power of 2. Each node i is connected to nodes 2i mod N and (2i+1) mod N. Although the throughput of this system is higher than that of the bidirectional loop, it does not make geographical sense and can only be used feasibly in a small area. Since N is constrained to be a power of 2, there is no known way to add one node at a time. The network provides alternate paths between nodes, but they are much longer than the primary paths.
It is an object of this invention to provide an improved topology for a local area network.
It is a further object of the invention to increase the throughput and reliability of a local area network through an improved topology.
It is another object of the invention to provide a local area network topology with simple enlarging and routing schemes.
It is yet another object of the invention to provide a local area network topology which requires only one kind of connection, and is adaptable to a hierarchical structure.